Recherche et tri : les fondements des grandes quantités de données

La recherche et le tri ne sont pas seulement l'introduction du cours sur les algorithmes, mais constituent aussi la logique fondamentale de la gestion des données en informatique. La valeur des données dépend de l'efficacité avec laquelle elles peuvent être récupérées et organisées. Cette section explore à travers la recherche séquentielle, la plus basique des méthodes,recherche séquentiellele cœur de l'évaluation des algorithmes : comment localiser une cible par comparaison linéaire dans différentes formes de données.

1. Logique et coût

Recherche séquentielle :Commencez par le premier élément de la liste et examinez-les un par un selon l'ordre par défaut jusqu'à trouver l'élément cible ou parcourir toute la liste. Son complexité temporelle est $O(n)$.

2. Comparaison des performances : désordonné vs ordonné

Dansla liste désordonnée中（见下表），无论成功与否，平均比对次数通常与 $n$ 成正比。而在la liste ordonnéel'utilisation de la règle d'organisation des données permet d'obtenir une « interruption anticipée » : dès qu'un élément plus grand que la cible est rencontré, on peut conclure que la cible n'existe pas. Bien que cela n'altère pas fondamentalement la complexité $O(n)$, il améliore l'efficacité moyenne des recherches infructueuses.